For 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)

0
votes
1answer
48 views

Tiling problem : Number of ways a floor can be tiled

Find number of ways a floor n meter length and 11 meter wide can be floored with tiles of 2 cm length and 1 cm wide wide tiles without breaking the tiles (assume n is even) Could you please help in ...
-2
votes
1answer
27 views
-1
votes
0answers
25 views

Number of simple, connected graphs with K edges and N distinctly labelled vertices [on hold]

Ok. I'm aware of this question and answer, but it's over my head. I've written a recursive function that I thought would do the job, but it doesn't, apparently. Could someone explain to me why it's ...
4
votes
2answers
60 views

No Adjacency Combinatorics Problem via Generating Function

I would like to find the generating function solution for the following combinatorics/probability problem. I have a combinatorial solution and the generating function deduced thereof. But I can not ...
8
votes
1answer
193 views
+200

Finding real money on a strange weighing device

You have 50 coins which each weigh either 20 grams or 10 grams. Each is labelled from 0 to 49 so you can tell the coins apart. You have one weighing device as well. At the first turn you can put as ...
2
votes
0answers
6 views

Special class of Brenke Polynomials

I was wondering if there are any particular papers dealing with a particular class of Brenke Polynomials, defined as $$A(t)B(xt)=\sum_{n\ge 0}P_n(x)t^n$$ where $A=B$ or, where $A(t)=C(B(t),t)$ for a ...
4
votes
1answer
150 views

Why aren't there 21 players in this tournament?

In a tournament each player played exactly one game against each of the other players. In each game the winner was awarded 1 point, the loser got 0 points, and each of the two players earned ...
3
votes
2answers
76 views

Among $k$ consecutive numbers one has sum of digits divisible by $11$

Find the least positive integer $k$ with the property that given any $k$ consecutive positive integers, there is at least one whose sum of digits is divisible by $11$. I can show for $k\leq 57$. ...
3
votes
1answer
58 views

Another Evaluation of the Ramsey number $\mathcal{R}(3,3,3)$

The problem Show that $\mathcal{R}(3,3,3)=17$ The story behind the problem and some notation It was first proven by Greenwood and Gleason in 1955 in their paper Combinatorial relations and ...
0
votes
2answers
26 views

Student card handing Inclusion–exclusion principle

I got the following question and would very much appreciate any help with understanding it solution. "5 Student cards are handed to 5 students so that each student gets 1 student card, what is the ...
1
vote
1answer
12 views

How many Schedules possible with given set of Transactions? Given that total ordering of operations in a transactions is there.

Given that : There are $m$ transactions = $\{T_1, T_2, \dots, T_m\}$ and for each transaction $T_i$ there are $n_i$ operations in it. It is required that the relative ordering of operations within ...
1
vote
3answers
101 views

Binomial Sum: Values

I need this as lemma. Regard the sums: $$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$ Then it holds: $$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$ How can I check ...
-1
votes
1answer
29 views

Functions from $\{w,x,y,z\}$ to $\{a,b,c\}$

I'm having some problems understanding how functions and Big-O notation works... I've checked a couple of other threads here but still unsure Let's say I have $A = \{w, x, y, z\}$ and $B = \{a, b, ...
0
votes
1answer
37 views

How do I prove the formula for multichoose?

In combinatorics, there is a formula "$n$ multichoose $k$", which is the way of making a multiset having $k$ elements choosing out of $n$ options. "$n$ multichoose $k$" is the same as "$(n+k-1)$ ...
-2
votes
0answers
55 views

How many increasing functions $f:\{1,\ldots,n\} \to \{1,2,\ldots,n\}$ are there such that $f(i) \ge i , \forall i=1(1)n$ , where $n \in \mathbb N$?

Let $n\in \mathbb N , n \ge 3$ . How many increasing functions $f:\{1,,\ldots,n\} \to \{1,2,\ldots,n\}$ (i.e. $f(i) \ge f(j) , \forall i=1(1)n$ ) are there such that $f(i) \ge i , \forall i=1(1)n$ ?
2
votes
1answer
24 views

combinatorics problem: find all possible ordered permutations in a tuple

I have a tuple that looks like this: $(1,2,3,4)$ I want to generate all possible nested tuples that can be made from the original tuple which maintain the original order of the array. For the ...
3
votes
2answers
80 views

Probability with changing number of marbles

Given a bag containing 20 marbles of 5 different colors in this configuration: 8x Blue 6x Red 3x Green 2x White 1x Black How would you determine the probability of picking a marble of a specific ...
1
vote
2answers
30 views

Simple counting question- numbers in sequences.

I'm taking a counting/probability course. Got this one question that I originally thought was simple, but my solution turned out to be wrong. "How many $6$-digit sequences have a digit that appears ...
0
votes
0answers
15 views

Enumeration of skew Ferrers diagrams revisited.

In M. P. Delest, J. M. Fedou, "Enumeration of skew Ferrers diagrams", Discrete Mathematics. vol.112, no.1-3, pp.65-79, (1993) http://dx.doi.org/10.1016/0012-365X(93)90224-H a generating function is ...
2
votes
2answers
53 views

Probability Modem is Defective

A store has 80 modems in its inventory, 30 coming from Source A and the remainder from Source B. Of the modems from Source A, 20% are defective. Of the modems from Source B, 8% are defective. ...
0
votes
1answer
24 views

number of binary strings with equal number of 0's and 1's

I am trying to count the number $S$ of binary strings with equal number of 0's and 1's. Since this boils down to picking $n$ out of $2n$ places where 0's can fall into, my ansatz is $$ S = ...
0
votes
3answers
39 views

Girls and boys ordering combinatorics

I have the following combinatorics question but I don't know how to approach it: "10 girls and 4 boys are about to be photographed in a row, how many ordering options are there if between each 2 ...
0
votes
1answer
27 views

Balls and Boxes Generalization

Recently, I saw a problem here on MSE: $$$$"Put 9 pigs in 4 pens such that there are an odd number of pigs in each pen." Individual cases or solutions to the problem are quite easy. But how would we ...
0
votes
0answers
26 views

Probability at the end of a conditional chain where a random integer has been successively compared to various values

I have a series of IF, ELSE IF, ..., ELSE statements that ultimately give only two outcomes. I wish to describe in terms of probability the odds for these outcomes. I did most of it already but I ...
1
vote
1answer
27 views

Lower bound for the size of a maximal matching in a general graph

Let $G=(V,E)$ be a graph, let $M\subseteq E(G)$ be a maximal matching, and let $M^\star\subseteq E(G)$ be a maximum matching. Prove that $|M|\ge |M^\star|/2$. Any hints on how to prove this?
5
votes
1answer
85 views

The vertices of the $n$-cube are painted in two colors

The vertices of the $n$-dimensional cube are painted in two colors. The number of vertices of each color is the same ($2^{n-1}$). Prove that at least $2^{n-1}$ edges connect vertices of different ...
-3
votes
0answers
27 views

Suppose a sequence of 8 nucleotides contains 2 each of A, C, G, T. How many such sequences are there? [closed]

Suppose a sequence of 8 nucleotides contains 2 each of A, C, G, T. How many such sequences are there? please post the solution..
7
votes
0answers
50 views

Dominating a Four Dimensional Chessboard with Rooks

There is a family of chess problems where you try to dominate a board with as few copies of a given piece as possible. The chessboard is dominated if every square either contains a piece, or is ...
0
votes
1answer
27 views

How many sequences of lenght 2n, made of n “+1”s and n “-1”s and such that every partial summation of the first k terms is nonnegative, are there?

What's the number of sequences $$(u_{1},...,u_{2n})$$ with $u_{i}=+1,-1$, such that: $$\sum_{j=1}^{2n} u_{j}=0\quad\hbox{and}\quad \sum_{j=1}^{k} u_{j}\geq 0$$ I realized that $u_{1}=+1$ and ...
-1
votes
2answers
44 views

How many ways can the players enter? [closed]

$5$ players want to enter a stadium through three gates of the stadium, However, each gate of the stadium can only pass two players. How many ways can the players enter the stadium?
6
votes
1answer
62 views

Poker Combinations: How many ways can you get 4 of the same suit in a hand of 5 cards?

The homework question is: in how many ways can we get exactly 4 cards of the same suit in a hand of 5 cards? (Order does not matter.) Here is what I have: we need to pick two different suits, decide ...
-3
votes
0answers
30 views

Write a recurrence relation [closed]

Write a recurrence relation for the value of a binomial coefficient, and explain why it makes sense. I was getting: Using a Pascal's triangle looking at row 5 that (x + y)5 = 1 x5 + 5 x4y + 10 x3y2 + ...
2
votes
2answers
26 views

Is this equivalent to Szemerédi's theorem?

I know that Szemerédi's theorem states that any set of integers with positive natural density contains arbitrary long arithmetic progressions. However, does this imply that such a set contains an ...
2
votes
1answer
32 views

Let $S = \{1,2,3,…,1992\}$ find the number of subsets $\{a,b,c\}$ such that $3\mid(a+b+c)$.

Let $S = \{1,2,3,...,1992\}$ find the number of subsets $\{a,b,c\}$ such that $3\mid(a+b+c)$. I managed to solve the same problem but with 2-elements sets in the following way: Make the ...
1
vote
1answer
45 views

What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?

What is the combinatorial proof for the formula of Stirling numbers of the second kind ? i.e. S(n,k) where n is the number of objects and k is the number of parts $${n\brace ...
1
vote
1answer
39 views

Expectation value of number of trials to select all tokens with replacement

(I suppose this is analogous to the coupon collector's problem) I have an infinitely large bag containing tokens marked equiprobably with a number from 1 to $k$ i.e. the probability of selecting any ...
-1
votes
1answer
21 views

Count of boolean functions satisfying a condition [closed]

How to find the number of boolean functions of n variables with the given property: If $f(\alpha) = 1$, where $\alpha \in J^2_n$, then $\forall \beta \in J^2_n : w(\beta) \ge w(\alpha) \implies ...
1
vote
2answers
40 views

Probability of winning (dice)

Given a simple dice $\{1,2,3,4,5,6\}$ : A win is defined as a sequence of $1 \to 2 \to 3$. Every result which "breaks" the sequence (e.g. $1\to 2 \to 1$), is forcing us to start all over again. What ...
3
votes
4answers
63 views

How to solve this combinatorics problem?

As a tourist in NY, I want to go from the Grand Central Station (42nd street and 4th Avenue) to Times Square (47th street and 7th Avenue). I needed my morning coffee, and wanted to go to a Starbucks ...
0
votes
2answers
40 views

Number of permutation with condition

Assume we have a group consisting of both women and men. (In my example it is 67 women and 43 men but that is not important.) The women are indistinguishable and the men are also indistinguishable. ...
3
votes
3answers
60 views

Number of subsets

Let $|X|=n$. How to find all number of subsets $X$ consisting of an even number of elements?
3
votes
2answers
55 views

In how many ways can you group $3$ different numbers from $1$ to $12$ wherein their sum is divisible by $3$?

In how many ways can you group $3$ different numbers from $1$ to $12$ wherein their sum is divisible by $3$? This question is one of the questions asked in a Math contest for intermediate level, ...
2
votes
2answers
64 views

100 prisoners 100 boxes problem

I have some issues with a problem I found on this page: http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf The problem goes as follows: "A group of 100 condemned prisoners are offered the ...
1
vote
1answer
79 views

Simplify a Combinatorial Sum $\sum_{k=0}^\infty {a\choose k}{b\choose c-k}{d-k\choose e}$

Is there a way to simplify $$\sum_{k=0}^\infty {a\choose k}{b\choose c-k}{d-k\choose e}$$ where $a,b,c,d,e$ are natural numbers? In particular, I would like to see the case for $a=45, ...
7
votes
1answer
99 views

How many ways to add to 32?

I have been presented with a rather complex combination problem. Using only the numbers 2, 4, 6 and 8, how many possible ways can you add up to 32 if the number 4 may only be used no more than once ...
2
votes
1answer
65 views

unbalancing lights

I'm reading the following notes on unbalancing lights, http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf. The question i have is regarding the first page. Where it says Consider a square $n ...
0
votes
2answers
34 views

How many non-negative integer solutions does $x_1+x_2+\cdots+x_n=A$ have?

If I have the Diophantine equation $\displaystyle{\sum_{i=1}^n x_i =A}$, is there a function $f(n,A)$ that will yield the number of non-negative integer solutions of the equation?
1
vote
1answer
19 views

Number of ways of selecting all k-indexed identical items before all k+1 indexed identical items for all k from 1 to n

Suppose we have n indices and we have a specific number of items allotted to this index. Say for 2 balls of colors Blue(B)[1], 4 of color Green(G)[2] and 2 of color Red[3] (I could've just assigned ...
3
votes
2answers
75 views

Partitioning $\{1,2,\cdots ,n\}$ into $2$ sets guarantees $3$ numbers $a,b,c$ in the same set with $ab=c$ for some $n$

(ISL-20-$1988$) Find the least natural number $ n$ such that, if the set $ \{1,2, \ldots, n\}$ is arbitrarily divided into two non-intersecting subsets, then one of the subsets contains 3 distinct ...
8
votes
2answers
193 views
+50

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...