This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

6
votes
1answer
137 views

My fun conjecture about linearly independence

In the $\mathbb{R}^n$ vector space, there are distinct $m$ vectors $v_i$'s ($1< i\leq m)$ such that each component has value 0 or 1. Let $A_i$ be the set of $j$'s where $j$-th component of $v_i$ ...
2
votes
0answers
29 views

Probability that half the nodes has more than half out-degree

This is something I just wondered about, and I don't know whether there is a closed-form answer or not. I've tried but without making progress, so any idea would be helpful. Consider a complete graph ...
3
votes
1answer
59 views

What is the joint probability distribution of number of balls after $n$ draws?

The following problem came into my mind when I am studying the Polya Urn Model. At the beginning, from a bin containing $c_1$ balls labeled $1$, $c_2$ balls labeled $2$, … , $c_m$ balls labeled $m$, ...
0
votes
3answers
63 views

Inclusion-Exclusion Principle for basic combinatorics problem…

How many ways are there to pick five people for a committee if there are six (different) men and eight (different) women and the selection must include at least one man and one woman? I know ...
0
votes
2answers
46 views

SAT Math probability and repeats

A ball's area is divided into two sections. If each section is to be painted using one of 5 different colors, how many differently painted designs are possible? I know that the first area has 5 ...
3
votes
1answer
312 views

Permutations of a set with a conditional subset

Using the digits 1, 2, 3, 5, 6, 8, 0 only once, how many 4-digit numbers could be constructed if the number is even? This is an exercise from an online course I'm taking. The given solution suggests ...
2
votes
2answers
1k views

A general form for a function of parameters which reduces to Harmonic number when all parameters are =

Looking for the general form $f_n$ a solution for an integral with $n$ strictly positive parameters $\beta_i$, $\beta_1,\beta_2,\ldots, \beta_n$ . The integral is as follows $$ f_n=\int_0^\infty ...
1
vote
1answer
276 views

3 digit number is a unique number if no digit is repeating [duplicate]

A 3 digit number is a unique number if no digit is repeating. In how many ways 3 unique numbers can be chosen such that they do not have any digit in common?
15
votes
0answers
237 views

Making Friends around a Circular Table

I have $n$ people seated around a circular table, initially in random order. At each step, I choose two people and switch their seats. What is the minimum number of steps required such that every ...
1
vote
2answers
32 views

number of ways to stack n distinct objects into k distinct boxes

I know that number of ways to distribute $n$ distinct objects into $k$ distinct boxes is $k^n$, but there order of objects in a box doesn't matter. If we want to stack objects in a box, then order ...
0
votes
0answers
57 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
0
votes
1answer
23 views

Number of particular terms in a product

I hope this question is not too stupid, but I know very little about combinatorics and i can't find an answer.. So fix $r\in \mathbb{N}$. Let $x_1,\ldots, x_r$ be variables, let the product between ...
1
vote
1answer
52 views

52-card deck probability…

If 13 players are each dealt four cards from a 52-card deck, what is the probability that each player gets one card of each suit? So I chose to do the situation where we have no repetition (i.e ...
3
votes
2answers
96 views

Generating function: Probability regarding coin toss

If a coin is flipped 25 times with eight tails occurring, what is the probability that no run of six (or more) consecutive heads occur? Wasn't sure how to approach this and am quite positive my ...
0
votes
0answers
20 views

Finding integer vectors in the column space of a matrix

Consider a given set $S \subset Z$. $S$ is a finite set. Matrix $A \in S^{N \times M}$ is also given. Does there exist an algorithm to find all the vectors belonging to the space Col$(A)\cap S^N$ ...
1
vote
0answers
27 views

Name for variations of elements from several sets

Consider the set $S=\{1,2,3\}$. As is well known, $(1,1), (1,2), (1,3), (2,1), (2,3), \ldots, (3,3)$ are the variations with repetition of elements of $S$ taken two at a time. We can similarly ...
3
votes
0answers
51 views

number of Lattice paths from origin to diagonal after removing vertices

i am stuck with the following problem: consider the quarter plane $\mathbb{N}_0^2$ with vertices $(i,j)\in\mathbb{N}_0^d$ and edges from each vertex $(i,j)$ to $(i+1,j)$ and $(i,j+1)$, i.e. one ...
0
votes
2answers
81 views

Advanced Counting Puzzle

Suppose we have a house in which every room has an even number of doors. Prove that the number of doors from the house to the outside world is also even.
0
votes
1answer
257 views

I need a formula for how many ways I can choose k balls (two balls each time from the same box) from n boxes?

We have n (can take any value 1,2,3,...) boxes each has the same number of distinct marbles, say b marbles, so the total number of marbles S=n*b. we can choose marbles from boxes with the following ...
0
votes
1answer
16 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
1
vote
1answer
61 views

Divide and Conquer (recurrence relation problem)…

The problem: (a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers. (b) Give a recurrence relation for ...
5
votes
2answers
88 views

How to Count the number of words over an alphabet subject to restrictions on letter count?

For an alphabet $X$, is there a method of computing how many words over $X$ of length $n$ there are where the number of occurrences of each letter must satisfy a system of equations? For example if ...
1
vote
2answers
339 views

How to solve for the amount of arrangements of books on a shelf?

Having a little bit of trouble with this question, but I don't necessarily want the answer, I'm looking for an explanation on how to do it, and if my theory is correct. How many ways are there to ...
4
votes
1answer
54 views

Rearrange columns and rows of a matrix such that it can be split in half

I am not a mathematician, so please excuse me if this question turns out to be trivial. I need this at work, but I could not figure out how to solve this efficiently, though it looks like it might be ...
3
votes
0answers
55 views

A function on sets which is constant for all permutations

Let $U=\{1, 2,\ldots, 2014\}$. For positive integers $a$, $b$, $c$ we denote by $f(a, b, c)$ the number of ordered 6-tuples of sets $(X_1,X_2,X_3,Y_1,Y_2,Y_3)$ satisfying the following conditions: ...
3
votes
1answer
60 views

How many orientations are there for pawns (for a single player) on a chess board?

How many orientations are there for pawns on a chess board? Pawns can only move forward or diagonally forward. No two pawns may exist on the same square. Pawns start on the second row, and ...
0
votes
2answers
350 views

Finding Coprime triplets

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor. Example : Let N=4 ...
5
votes
1answer
77 views

Binomial Congruence

How can we show that $\dbinom{pm}{pn}\equiv\dbinom{m}{n}\pmod {p^3}$ for positive integers m and n and p a prime greater than 5? I can do it for mod p^2 but Im stuck here.
2
votes
2answers
54 views

Why is $\sum_{k=0}^{n} f(n,k) = F_{n+2}$?

If $f(n,k)$ is the number of $k$ size subsets of $[ n ] = { 1 , \ldots , n }$ which do not contain a pair of consecutive numbers, how can I show that $\sum_{k=0}^{n} f(n,k) = F_{n+2}$? ($F_{n}$ is the ...
1
vote
4answers
47 views

Possible arrangements of marbles in bags?

I've come across a question on a math test asking, "How many different ways can you put a dozen identical marbles into six bags so that each bag has atleat one marble in it?". I would imagine that ...
2
votes
2answers
62 views

Generating function of $a_n = \sum_{k = 0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k}\frac{(2k)!}{k!2^k}$ is $e^{x+x^2/2}$?

I need to prove that the generating function of $a_n = \sum\limits_{k = 0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k}\dfrac{(2k)!}{k!2^k}$ is $e^{x+x^2/2}$. I tried it like this. I know that ...
0
votes
1answer
39 views

Straight in 52cards+2Joker

I have 52card (ace to king) + 2Joker I'm supposed to compute how much straights of 5 cards I can make, excluding the straight flushes (straights with all cards being the same color) My reasoning is : ...
3
votes
1answer
42 views

A bijection defined on the set of configuration of lamps

Consider $n$ lamps clockwise numbered from $1$ to $n$ on a circle. Let $\xi$ to be a configuration where $0 \le \ell \le n$ random lamps are turned on. A cool procedure consists in perform, ...
0
votes
1answer
26 views

Distinguishing between two sets of tournament partition

A "tournament" is a complete graph such that each edge is directed one way or the other (but not both). Does there exist a tournament of size $2n$ such that we can partition it into two sets $A,B$, ...
0
votes
1answer
34 views

Simple Combinations

Question: Class consists of $7$ men and $5$ women. Find number of committees of five that can be selected from the class if the committee is to consists of at least one man and at least one woman. My ...
0
votes
1answer
33 views

Game of coins with two players

Two Players play a game as follow : Given total N coins where x coins are of red color and y coins of blue color. Now Player1 selects a coin from the heap of coin and put it in a line on table. Then, ...
0
votes
1answer
25 views

Möbius function for posets and primes

Let the Möbius function $\mu_P : P \times P \rightarrow \mathbb{Z}$ for a poset $P$ be defined as $$\mu_P(x,y) = \begin{cases} 0 & x \not\leq y \\ 1 & x = y \\ - \sum\limits_{x \leq z < ...
8
votes
1answer
131 views

Tricky (extremal?) combinatorics problem

Apologies for being unsure the best way to express this problem. I have 9 tables with 4 students at each table. I want to re-seat all students so no two students who have sat together ever sit ...
1
vote
2answers
46 views

Properties of bijections

If a bijection exists between set A={a1, a2, ...} and set B={b1, b2, ...} such that a1 maps to b1 and a2 maps to b2, etc., does this mean if we find a relationship R between a1 and b1 (i.e. f(b1) is ...
2
votes
3answers
103 views

Number of ways, powers of $2$ sum up specific values

Given the set $B=\{2^0,2^1, 2^2,...2^{n-1} \}$. Now you pick $n$ elements of $B$ with repetitions and sum the picked elements, e.g. picking every element once this sums up to ...
1
vote
1answer
25 views

What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
0
votes
1answer
21 views

Simple Permutations/Combinations Question

A group of 5 men and 5 women stand in line to have their photo taken. How many ways can they stand in line if no two men and no two women stand together? My method: _M_M_M_M_M_ Male * Female = 5P5 ...
5
votes
6answers
179 views

The physical meaning of ${n \choose k} = {n \choose n-k}$.

They say that $${n \choose k}={n \choose n-k}.$$ Can someone explain its physical meaning? Among many problems that use this proof, here is an example: The english alphabet has $26$ letters ...
6
votes
4answers
122 views

The number of permutations of $\{1,2,\ldots,n\}$ that have exactly one ascent (rise).

Sloane's OEIS A000295 counts the number of $n$-permutations with exactly one ascent. For example $a(3)=4$ because we have: $1\wedge32$, $21\wedge3$, $2\wedge31$, $31\wedge2$ where I have marked the ...
2
votes
2answers
60 views

Counting problem: selecting $n$ objects among $k$ infinite collections.

Here's a counting question that got me thinking. Unfortunately, I couldn't get around it. Need help. You are given $k$ distinct coloured boxes. In each box, lies infinite balls of the same colour as ...
35
votes
1answer
531 views

What is that curve that appears when I use $\ln$ on Pascal's triangle?

I made a little program that generates Pascal triangles as images : I first tried it associating to each pixel a color whose intensity was proportional to the number in the Pascal triangle The ...
0
votes
1answer
85 views

Advanced Counting Problem [closed]

1) How many positive integers are there whose digits strictly increase from left to right? (For example, 28, 13589, and 4 are all such integers. "Strictly" means no two digits can be equal, so 15668 ...
4
votes
4answers
89 views

Calculate the number of different words, where $0$ appears an even number of times.

Let the set of words with an even length $n$ from the alphabet: $\{ 0,1,2\}$. Calculate the number of different words, where $0$ appears an even number of times. For example, for $n=6$ , the words ...
0
votes
1answer
26 views

How to calculate the number of points in the interior and on the boundary of these figures with vertices as lattice points?

We define a point $(x,y)$ in the plane to be a lattice point if both $x$ and $y$ are integers. Now let $$S\colon= \{ (x,y) \ | \ 0 \leq x \leq m, \ 0 \leq y \leq \frac{nx}{m} \}, $$ where $m$ and ...
0
votes
0answers
50 views

How to establish this result using induction?

A point $(x,y)$ in the plane is called a lattice point if both coordinates $x$ and $y$ are integers. Let $P$ be a polygon whose vertices are lattice points. Then the area of $P$ is $I + \frac{1}{2}B ...